Comparison of Different Tree Implementations

Each of the designs has its own strengths and weaknesses. The strengths and weaknesses are discussed in this lesson, and a table summarizes them all.

Pros and cons of different tree implementations#

Here are some of the strengths and weaknesses of each design that we may consider:

• Adjacency List is the most conventional design, and many software developers recognize it.
• Recursive Queries using WITH or CONNECT BY PRIOR make it more efficient to use the Adjacency List design, provided that we use one of the database brands that support the syntax.
• Path Enumeration is good for breadcrumbs in user interfaces, but it’s fragile because it fails to enforce referential integrity and stores information redundantly.
• Nested Sets is a clever solution — maybe too clever. It fails to support referential integrity. It’s best used when we need to query a tree more frequently than we need to modify it.
• Closure Table is the most versatile design and the only design in this chapter that could allow a node to belong to multiple trees. It requires an additional table to store the relationships. This design also uses a lot of rows when encoding deep hierarchies, increasing space consumption as a trade-off for reducing computing.

We choose the design on the basis of how efficiently we can perform the operation we need to perform using that design. In the table below, operations are marked as either easy or hard to perform when using each of the respective tree designs.

There’s more to learn about storing and manipulating hierarchical data in SQL. A good book that covers hierarchical queries is Joe Celko’s Trees and Hierarchies in SQL for Smarties. Another book that covers trees and even graphs is SQL Design Patterns by Vadim Tropashko. The latter book has a more formal, academic style.